package com.le.basic.matrix;

import java.util.Arrays;

/**
 * 岛问题
 * 一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右 四个位置相连，
 * 如果有一片1连在一起，这个部分叫做一个岛，求一个 矩阵中有多少个岛
 */
public class Code_10_IsLands {
    public static void main(String[] args) {
        int[][] m1 = {
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 0, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        };
        System.out.println(countLands(m1));
        printMatrix(m1);


        int[][] m2 = {
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 1, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 1, 1, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        };
        System.out.println(countLands(m2));
        printMatrix(m2);
    }

    public static void printMatrix(int[][] m){
        for (int i = 0; i < m.length; i++) {
            System.out.println(Arrays.toString(m[i]));
        }
    }

    public static int countLands(int[][] m){
        if (m == null){
            return 0;
        }
        int row = m.length;
        int column = m[0].length;
        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (m[i][j] == 1){
                    res++;
                    infect(m,i,j,row,column);
                }
            }
        }

        return res;
    }

    private static void infect(int[][] m, int i, int j, int row, int column) {
        if (i < 0 || i >= row || j < 0 || j >= column || m[i][j] != 1){
            return;
        }
        m[i][j] = 2;
        infect(m,i,j-1,row,column);
        infect(m,i,j+1,row,column);
        infect(m,i-1,j,row,column);
        infect(m,i+1,j,row,column);
    }
}
